1. Field of Invention
This invention is directed to the systems and methods for constructing weighted finite-state automata used to represent grammars.
2. Description of Related Art
Context-free and context-dependent grammars are used in a variety of technical fields, such as linguistics, speech recognition and speech synthesis (text-to-speech), to represent the conversion of one set of symbols into another set of symbols. For example, in context-dependent linguistic rewrite rules, the grammar defines how elements of a language can be combined based on the context in which those elements appear. Similarly, context-free grammars can be used to convert acoustic signals into recognized speech.
Grammars generally comprise a large number of rules, where each rule defines how a given string of symbols can be produced from a different series of symbols. In many computer-implementations, such grammars are represented or implemented using finite-state automata. If the grammar is a weighted grammar, the weighted grammar is represented as a finite-state transducer. Representing grammars using finite-state automata or transducers is often crucial, as finite-state automata or transducers can be optimized by compacting, or determinizing and minimizing, the finite-state automata or transducers.